package gold.digger;

import gold.utils.InputUtil;
import org.stringtemplate.v4.ST;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC664 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public int strangePrinter(String s) {
            int n = s.length();
            if (n == 0) {
                return 0;
            }
            int[][] dp = new int[n][n];
            for (int i = n; i >= 1; i--) {
                for (int j = i; j <= n; j++) {
                    if (i == j) { // 只有一个元素时
                        dp[i - 1][j - 1] = 1;
                    } else if (s.charAt(i - 1) == s.charAt(j - 1)) { // s[i]==s[j]
                        dp[i - 1][j - 1] = dp[i - 1][j - 2];
                    } else { // 有多个元素，且s[i]!=s[j]
                        int min = Integer.MAX_VALUE;
                        for (int x = i; x < j; x++) {
                            min = Math.min(min, dp[i - 1][x - 1] + dp[x][j - 1]);
                        }
                        dp[i - 1][j - 1] = min;
                    }
                }
            }
            return dp[0][n - 1];
        }
    }

    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC664 an = new LC664();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
